package com.justnow.offer;

/**
 * @author justnow
 * Created on 2020-09-15
 * Description
 * 对称二叉树
 * 对于树中任意两个对称节点L和R，一定有：
 * L.val = R.val：即此两对称节点值相等
 * L.left.val = R.right.val：即L的左子节点和R的右子节点对称。
 * L.right.val = R.left.val：即L的右子节点和R的左子节点对称。
 */
public class Solution49 {

    /**
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }

        return recur(root.left, root.right);
    }

    private boolean recur(TreeNode root1, TreeNode root2) {
        //递归终止的条件共三个
        //1. root1和root2同时越过叶节点：此树从顶值底的节点都对称，因此返回true。
        if (root1 == null && root2 == null) {
            return true;
        }

        //2. root1或root2只有一个越过叶节点：此树不对称，因此返回false；
        if (root1 == null || root2 == null) {
            return false;
        }

        //3. 当root1的值与root2的值不相同：此树不对称，因此返回false；
        if (root1.val != root2.val) {
            return false;
        }

        /**
         *         1
         *      2     2
         *   3   4  4   3
         * 判断第三层的时候，注意两个节点的判断顺序
         */
        return recur(root1.left, root2.right) && recur(root1.right, root2.left);
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        this.val = x;
    }
}